All-Pairs Shortest Paths
•Find the distance between
every pair of vertices in a
weighted directed graph G.
•We can make n calls to
Dijkstra’s algorithm (if no
negative edges), which
takes O(nmlog n) time.
•Likewise, n calls to Bellman-
Ford would take O(n2m)
time.
•We can achieve O(n3) time
using dynamic
programming (similar to the
Floyd-Warshall algorithm).
Algorithm AllPair(G) {assumes vertices 1,…,n}
for all vertex pairs (i,j)
if i = j
D0[i,i] 0
else if (i,j) is an edge in G
D0[i,j] weight of edge (i,j)
else
D0[i,j] +
for k 1 to n do
for i 1 to n do
for j 1 to n do
Dk[i,j] min{Dk-1[i,j], Dk-1[i,k]+Dk-1[k,j]}
return Dn
k
j
i
Uses only vertices
numbered 1,…,k-1 Uses only vertices
numbered 1,…,k-1
Uses only vertices numbered 1,…,k
(compute weight of this edge)